package com.heima.leetcode.practice;

import java.util.Map;

/**
 * 2485 找出中枢整数
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/13 10:50
 */
public class E2485 {

    /**
     * <h3>方法一：遍历，分别对两边求和比较</h3>
     * @param n 待处理数
     * @return 中枢整数
     */
    public int pivotInteger1(int n) {
        for(int i = 1; i <= n; i++){
            int prev = ((1 + i) * i) >> 1;
            int next = ((i + n) * (n - i + 1)) >> 1;
            if(prev == next){
                return i;
            }
        }
        return -1;
    }

    // 1 + 2 + ... + x == (1 + x) * x / 2
    // x + (x + 1) + (x + 2) + ... + n == (x + n) * (n - x + 1) / 2
    // 建立等式：(1 + x) * x / 2 == (x + n) * (n - x + 1) / 2
    // 求解：x = sqrt((n + n^2) / 2)

    /**
     * <h3>方法二：建立等式推算</h3>
     * @param n 待处理数
     * @return 中枢整数
     */
    public int pivotInteger2(int n){
        int t = (n + n * n) >> 1;
        int sqrt = (int) Math.sqrt(t); // n * (n + 1) / 2必定是整数
        if (sqrt * sqrt == t){
            return sqrt;
        }
        return -1;
    }
}
